package cn.cqsztech.algo.bt;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * ccmars
 * 2022/3/16
 * 判断二叉树是否相同
 **/
public class BinaryTree {
    /**
     * 递归判断两个二叉树是否相同
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean chargeIsSame(MyNode a, MyNode b) {
        if (a == null ^ b == null) {
            return false;
        }
        if (a == null && b == null) {
            return true;
        }
        return a.val == b.val && chargeIsSame(a.left, b.left) && chargeIsSame(a.right, b.right);
    }

    public static void main(String[] args) {
        MyNode a = new MyNode();
        a.val = 1;
        a.left = new MyNode();
        a.left.val = 2;
        a.right = new MyNode();
        a.right.val = 3;
        MyNode b = new MyNode();
        b.val = 1;
        b.left = new MyNode();
        b.left.val = 2;
        b.right = new MyNode();
        b.right.val = 3;
        System.out.println(chargeIsSame(a, b));
        System.out.println(isMirrorBT(a, a));
        int[] pre = {3, 9, 20, 15, 7};
        //中序遍历
        int[] ind = {9, 3, 15, 20, 7};
        System.out.println(buildTree(pre, ind));
    }

    /**
     * 判断二叉树是否是镜像二叉树
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean isMirrorBT(MyNode a, MyNode b) {
        if (a == null ^ b == null) {
            return false;
        }
        if (a == null && b == null) {
            return true;
        }
        return a.val == b.val && isMirrorBT(a.left, b.right) && isMirrorBT(a.right, b.left);
    }

    /**
     * 判断数的深度
     *
     * @param node
     * @return
     */
    public static int maxDeep(MyNode node) {
        if (node == null) {
            return 1;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return Math.max(maxDeep(node.left), maxDeep(node.right)) + 1;
    }

    /**
     * LeetCode105题目根据二叉树的中序和前序得到一颗二叉树
     * 该二叉树中没有重复的数据
     */
    public static MyNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        if (preorder.length != inorder.length) {
            throw new RuntimeException("输入有误,无法构造二叉树");
        }
        return doC(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /**
     * @param pre 先序遍历的数组
     * @param L1  左子树的开始下标
     * @param R1  左子树的结束下标
     * @param in  中序遍历的数组
     * @param L2  右子树的开始下标
     * @param R2  右字数的结束下标
     * @return
     */
    public static MyNode doC(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
        //
        if (L1 > R1) {
            return null;
        }
        MyNode head = new MyNode(pre[L1]);
        //表示没有子节点了
        if (L1 == R1) {
            return head;
        }
        //找到中序遍历的头节点下标
        int find = L2;
        for (int i = L2; i < in.length; i++) {
            if (in[i] == pre[L1]) ;
            find = i;
            break;
        }
        //前序遍历3,9,20,15,7
        //中序遍历9,3,15,20,7 在中序中的头节点的index为1，则左子树的长度就是1-0+1-1,1-0+1表示到1有几个数,-1表示排除头结点
        head.left = doC(pre, L1 + 1, L1 + find - L2 + 1 - 1, in, L2, find - 1);
        head.right = doC(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
        return head;
    }

    /**
     * 二叉树的层序遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> levelOrder(MyNode root) {
        List<Integer> result = null;
        if (root == null) {
            return result;
        }
        result = new ArrayList<>();
        Queue<MyNode> q = new LinkedList<>();
        q.add(root);
        while (q.peek() != null) {
            MyNode poll = q.poll();
            if (poll.left != null) {
                q.add(poll.left);
            }
            if (poll.right != null) {
                q.add(poll.right);
            }
            result.add(poll.val);
        }
        return result;
    }
}
